package interview;

import org.junit.jupiter.api.Test;

public class FindValueMaxSonArray {
    private int[] arr = new int[]{-20, 1, -40, -50, 8, -1, 6, 4, 7, 8, -2, 9, -100, 100000};

    /**
     * 常规方法,时间复杂度O（n*n）
     * 先从第一个元素开始向后累加，
     * 每次累加后与之前的和比较，保留最大值，
     * 再从第二个元素开始向后累加，以此类推。
     */
    @Test
    public void forceSolve() {
        int i, j, maxValue, currentValue = 0, head = 0, end = 0;
        maxValue = arr[0];
        for (i = 0; i < arr.length; i++) {
            maxValue = arr[i];
            head = end = i;
            for (j = i + 1; j < arr.length; j++) {
                currentValue += arr[j];
                if (currentValue > maxValue) {
                    maxValue = currentValue;
                    head = i;
                    end = j;
                }
            }
        }

        System.out.println("head: " + head + "; end: " + end + "; maxValu: " + maxValue);
    }

    /**
     * 最优方法，时间复杂度O（n）
     * 和最大的子序列的第一个元素肯定是正数
     * 因为元素有正有负，因此子序列的最大和一定大于0
     */
    @Test
    public void lineTime() {
        int i, j, maxValue, currentValue, head = 0, end = 0;
        maxValue = 0;
        currentValue = 0;
        for (i = -1, j = 0; j < arr.length; j++) {
            if (arr[j] > 0 && i < 0) {
                head = i = j;

            }

            currentValue += arr[j];
            if(currentValue > maxValue) {
                end = j;
                maxValue = currentValue;

                if(maxValue > 0) {
                    head = i;
                }
            }
            if (currentValue < 0) {
                currentValue = 0;
                i = -1;
            }
        }

        System.out.println("head: " + head + "; end: " + end + "; maxValu: " + maxValue);
    }
}
